package leetcode;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 14:46
 *
 * 分析：piles = [3,6,7,11], H = 8
 * 假设分析：如果每个小时吃3根，那么需要 1 + 2 + 3 +4=10个小时   不满足
 * 如何如果每个小时吃4根， 1 + 2 +2 + 3 = 8 满足
 * 如果美国小时吃5根：1 +2 + 2 + 3=8
 * 每个小时吃的越少，总用时间越长
 * 香蕉取值范围：1-11之间
 * k->eatingTime(k)  单调函数
 * 二分搜索
 * 先看中间值能不能吃完，再继续二分搜索----
 * eatingTime(k) < H的最大eatingTime对应的k
 *
 */
public class Solution875 {

    public int minEatingSpeed(int[] piles, int h) {


        int left = 1;
        int right = Arrays.stream(piles).max().getAsInt();
        while (left <right){
            int mid = left + (right-left)/2;
            //对于呵呵没小时吃mid个，需要几个小时吃完
            //如果这个时间小于h，我们需要去左边找找它的更小的解，这个解不能丢弃
            //所以是right=mid，包含
            if(eatingTime(piles,mid) <=h){
               right = mid;
            }else{
                left = mid + 1;
            }
        }

        return left;
    }

    private int eatingTime(int[] piles, int k) {
        int res=0;
        for(int pile:piles){
            //如果不能整除，需要额外多的一个小时吃
           res += pile/k + (pile % k > 0? 1:0);
        }
        return res;
    }


}
